#pragma once
#include<iostream>
#include<vector>
#include<list>
#include<queue>
#include<deque>
using namespace std;

namespace Wang
{

template<class T, class Container = deque<T>>
class stack
{
    Container _con;
public:
    void push(const T& x) { _con.push_back(x); }
    void pop() { _con.pop_back(); }
    T& top() { return _con.back(); }
    bool empty() { return _con.empty(); }
    size_t size() { return _con.size(); }
};

template<class T, class Container = deque<T>>
class queue
{
    Container _con;
public:
    void push(const T& x) { _con.push_back(x); }
    void pop() { _con.pop_front(); }
    T& front() { return _con.front(); }
    T& back() { return _con.back(); }
    bool empty() { return _con.empty(); }
    size_t size() { return _con.size(); }
};


template<class T>
struct myless
{
    bool operator()(const T& a, const T& b) const
    {
        return a < b;
    }
};

template<class T>
struct mygreater
{
    bool operator()(const T& a, const T& b) const
    {
        return a > b;
    }
};

template<class T, class Container = vector<T>, class Compare = myless<T>>
class priority_queue
{
    Container _con;

    // 向上调整
    void up(int i)
    {
        if(i == 0) return;
        int p = (i - 1) / 2;
        Compare cmp;
        if(cmp(_con[p], _con[i])) // 只需改用仿函数比较_con[p]与_con[i]的大小即可
        {
            swap(_con[i], _con[p]);
            up(p);
        }
        // 更喜欢用下面的写法，用匿名对象
        // if(Compare()(_con[p], _con[i]))
        // {
        //     swap(_con[i], _con[p]);
        //     up(p);
        // }
    }

    // 向下调整
    void down(int p)
    {
        int s = 2*p + 1;
        if(s >= _con.size()) return;
        Compare cmp;
        if(s + 1 < _con.size() && cmp(_con[s], _con[s + 1])) s++;
        if(cmp(_con[p], _con[s]))
        {
            swap(_con[s], _con[p]);
            down(s);
        }
    }
public:
    priority_queue() = default;

    // 迭代器区间构造
    template<class Iterator>
    priority_queue(Iterator first, Iterator last)
    {
        while(first != last) 
        {
            _con.push_back(*first);
            ++first;
        }
        // 从最后一个非叶子节点向下调整
        for(int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
            down(i);
    }
    // 下面的写法时间复杂度O(n*logn), 上面的写法时间复杂度O(n)
    // priority_queue(Iterator first, Iterator last)
    // {
    //     while(first != last) 
    //         push(*first);
    // }

    // 插入：尾插，然后向上调整
    void push(const T& x)
    {
        _con.push_back(x);
        up(_con.size() - 1);
    }
    
    // 删除堆顶：与最后一个元素交换，删除最后一个元素，然后向下调整
    void pop()
    {
        swap(_con[0], _con[_con.size() - 1]);
        _con.pop_back();
        down(0);
    }

    const T& top() const { return _con[0]; }
    size_t size() const { return _con.size(); }
    bool empty() const { return _con.empty(); }
};


}